package com.itheima.algorithm.linkedlist;

import java.util.Iterator;
import java.util.function.Consumer;

/**
 * 单项链表
 */
public class SinglyLinkedList implements Iterable<Integer> {
    /**
     * 头指针
     */
    Node head;

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = head;

            /**
             * 是否有下一个元素
             * @return
             */
            @Override
            public boolean hasNext() {
                return p!=null;
            }

            @Override
            public Integer next() {
                int value = p.value;
                p = p.next;
                return value;
            }
        };
    }


    /**
     * 节点类
     */
    private static class Node{
        /**
         * 值
         */
        int value;

        /**
         * 下一个节点指针
         */
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 向链表头部添加
     * @param value 待添加的值
     */
    public void addFirst(int value){
        head= new Node(value,head);
    }

    /**
     * 向链表尾部插入
     */
    public void addLast(int value){
        Node last = findLast();
        if(last == null){
            addFirst(value);
            return;
        }
        last.next = new Node(value,null);
    }

    private Node findLast(){
        //空链表
        if(head ==null){
            return null;
        }
        //链表非空
        // 初始指针
        Node p;

        for ( p =head;p.next!=null;p = p.next){

        }
        return p;

    }



    /**
     * 根据索引查找
     * @param index 索引
     * @return 找到，返回该索引位置节点的值
     *
     */
    public int get(int index){
        Node node = findNode(index);
        if(node == null){
            // 抛异常
            throw new IllegalArgumentException(
                    String.format("index [%d] 不合法%n",index));
        }
        return node.value;
    }

    /**
     * 向索引位置插入
     * @param index 索引
     * @param value 待插入值
     */
    public void insert(int index,int value){
        if(index == 0){
            addFirst(value);
            return;
        }
        // 找到上一个节点
        Node prev = findNode(index - 1);
        // 找不到
        if(prev == null){
            // 抛异常
            throw new IllegalArgumentException(
                    String.format("index [%d] 不合法%n",index));
        }
        prev.next = new Node(value,prev.next);
    }

    /**
     * 删除第一个元素
     */
    public void removeFirst(){

        if(head == null){
            // 抛异常
            throw new IllegalArgumentException(
                    "索引0不可删除");
        }

        // 链表非空 head指向第二个节点
        head = head.next;
    }

    public void remove(int index){
        // 删除第一个元素
        if(index == 0){
            removeFirst();
            return;
        }

        //找到上一个节点
        Node prev = findNode(index - 1);
        if(prev == null){
            //上一个节点未找到
            // 抛异常
            throw new IllegalArgumentException(
                    String.format("index [%d] 不合法%n",index));
        }
        //被删除的指针
        Node removed = prev.next;
        if(removed == null){
            // 抛异常
            throw new IllegalArgumentException(
                    String.format("index [%d] 不合法%n",index));
        }

        prev.next = removed.next;
    }



    private Node findNode(int index){
        int i=0;
        for(Node p = head;p!=null;p = p.next,i++){
            if(i ==index){
                return p;
            }
        }
        // 没有找到
        return null;
    }


    /**
     * 循环遍历
     * @param consumer 要执行的操作
     */
    public void loop1(Consumer<Integer> consumer){
        // 指针
        Node p = head;
        while (p!=null){
            consumer.accept(p.value);
            //更新节点,指针下移
            p = p.next;
        }
    }

    /**
     * 使用for循环改写
     * @param consumer 要执行的操作
     */
    public void loop2(Consumer<Integer> consumer){
        for(Node p = head;p!=null;p=p.next){
            consumer.accept(p.value);
        }
    }

    /**
     * 头结点指向递归函数
     */
    public void loop3(Consumer<Integer> before,Consumer<Integer> after){
        recursion(head,before,after);
    }


    /**
     * 针对某个节点进行的操作
     */
    private void recursion(Node cur, Consumer<Integer> before, Consumer<Integer> after){
        if(cur == null){
            return;
        }
        before.accept(cur.value);
        recursion(cur.next, before, after);
        after.accept(cur.value);
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(1);
        list.addLast(2);
        list.addLast(3);
        list.addLast(4);
        list.loop3(value ->{
            System.out.println("before:" +value);
        }, value ->{
            System.out.println("after:" +value);
        });

//        list.remove(0);

//        list.loop2(System.out::println);
//        list.test();
//        list.removeFirst();
//        list.removeFirst();

//        System.out.println(list.get(2));
//        System.out.println(list.get(10));

//        for (Integer value : list) {
//            System.out.println(value);
//
//        }

    }

}



